package Algorithm.array;

/**
 * @Desc:   最大子序和
 * @author: cww
 * @DateTime: 2020-04-28 0:28
 */

public class MaxSubArray {
    public static void main(String[] args) {
        maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4});
    }
    public static int maxSubArray(int[] nums) {
        int n = nums.length;
        int currSum = nums[0], maxSum = nums[0];

        for(int i = 1; i < n; ++i) {
            currSum = Math.max(nums[i], currSum + nums[i]);
            maxSum = Math.max(maxSum, currSum);
        }
        return maxSum;
    }

    public int maxSubArray1(int[] nums) {
        int ans = nums[0];
        int curr = 0;
        for(int i = 0;i<nums.length;i++){
            if(curr>0){
                curr += nums[i];
            }else{
                curr = nums[i];
            }
            ans = Math.max(curr,ans);

        }
        return ans;
    }

}
